import java.util.Stack;

/**
 * 32. 最长有效括号
 * https://leetcode-cn.com/problems/longest-valid-parentheses/
 */
public class Solutions_32 {
    public static void main(String[] args) {
//        String str = "(()";  // output: 2
        String str = ")()())";  // output: 4

        int result = longestValidParentheses(str);
        System.out.println(result);
    }

    /**
     * 解法一：栈
     */
    public static int longestValidParentheses(String s) {
        int res = 0;
        // 存储下标
        Stack<Integer> stack = new Stack<>();
        // 给定默认的分隔符索引为 -1
        stack.push(-1);

        char[] arr = s.toCharArray();
        for (int i = 0; i < arr.length; i++) {
            if (arr[i] == '(') {
                stack.push(i);
            } else {
                stack.pop();
                if (stack.isEmpty()) {
                    // 当前索引作为“分隔符”
                    stack.push(i);
                } else {
                    // 计算距离：当前索引 - 最近的分隔符索引
                    int count = i - stack.peek();
                    res = Math.max(res, count);
                }
            }
        }
        return res;
    }
}
